# -*- coding: utf-8 -*-

# 时间复杂度 n * lg(n)
# 空间复杂度 1

# 算法中使用到的名词说明
# 1、空间原址性
#   算法只需要常数个额外的临时空间
# 2、二叉树
#   包含根，左子树(二叉树)，右子树(二叉树)，并且三者不相交的数据结构
#   二叉树是一个度为2的有序树
#   eg: @表示为空
#                   1
#               2       3
#           4      @ @       7
#
#   注意：
#   有序树是不区分左右节点的
#   eg: @表示为空
#                   1
#               2       3
#           4      @ @       7

#                   1
#               2       3
#           @     4 7       @
#   上面这2棵树，是2颗相同的有序树，但是2颗不相同二叉树

#   属性说明:
#                   1(根节点)                  深度0
#               2       3(内部节点)             深度1
#           @     4 @       7(叶子节点)         深度2
#   树的高度 = 2

# 3、满二叉树
#   只有子节点和度为2的节点的树，不存在度为1的内部节点
#   eg: @表示为空
#                   1
#               2       3
#           @      @ 6       7
# 4、完全二叉树
#   所有子节点深度相同，并且所有内部节点的度都为2
#   eg: @表示为空
#                   1
#               2       3
#           4      5 6       7


def max_heapify(nums, heap_size, index = 0):
    l = 2 * index + 1;
    r = l + 1;
    largest = index;
    if l < heap_size and nums[l] > nums[largest]:
        largest = l;
    if r < heap_size and nums[r] > nums[largest]:
        largest = r;

    if largest == index:
        return nums;

    nums[largest], nums[index] = nums[index], nums[largest];

    return max_heapify(nums, heap_size, largest);


def build_max_heap(nums):
    for i in range(len(nums) // 2 - 1, -1, -1):
        max_heapify(nums, len(nums), i);
    return nums;

def sort(nums):
    build_max_heap(nums);
    for i in range(len(nums) - 1, -1, -1):
        nums[0], nums[i] = nums[i], nums[0];
        max_heapify(nums, i);
    return nums;

# print max_heapify([1,56,985,12,53,154,32], 7);
# print build_max_heap([1,985,56,12,53,154,32]);
print sort([1,56,985,12,53,154,32]);
